import timeit

'''
计算list列表的运行时间
'''


# 对于li，生成[0,1,2...10000)的方法
# li.append()
# li.insert()
# [] + []
# list()
# [x for x in ]


def t1():
    li = []
    for i in range(10000):
        li.append(i)


def t2():
    li = []
    for i in range(10000):
        li.insert(0, i)


def t3():
    li = []
    for i in range(10000):
        li += [i]


def t4():
    list(range(10000))


def t5():
    li = [x for x in range(10000)]


timer1 = timeit.Timer('t1()', setup='from __main__ import t1')
timer2 = timeit.Timer('t2()', setup='from __main__ import t2')
timer3 = timeit.Timer('t3()', setup='from __main__ import t3')
timer4 = timeit.Timer('t4()', setup='from __main__ import t4')
timer5 = timeit.Timer('t5()', setup='from __main__ import t5')

print("append的时间", timer1.timeit(100))  # 0.08
print("insert的时间", timer2.timeit(100))  # 2.18
print("[]+[]的时间", timer3.timeit(100))  # 0.09
print("list的时间", timer4.timeit(100))  # 0.023
print("[x for x]的时间", timer5.timeit(100))  # 0.04


'''
list操作的时间复杂度
list是顺序存储结构，所以对最后一个元素的操作是没什么影响的
index                 O(1)
index assignment      O(1)
append                O(1)
pop()                 O(1)
pop(i)                O(n)
insert(i,item)        O(n)
del operator          O(n)
iteration             O(n)
contains              O(n)
get slice[x:y]        O(n)
del slice             O(n)
set slice             O(n+k)
reverse               O(n)
concatenate           O(k)
sort                  O(nlogn)
multipy               O(nk)


dict操作的时间复杂度
copy                  O(n)
get item              O(1)
set item              O(1)
delete item           O(1)
contains(in)          O(1)
iteration             O(n)

'''

